package listbyorder.access001_100.test98;

import listbyorder.utils.TreeNode;

import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 10:27
 */
public class Solution1 {

    // 验证一颗树是否是二叉搜索树
    // 使用循环中序遍历的方式
    // 这里使用包装类Integer可避免初始值是极小值的情况
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Integer pre = null;
        // 写一个中序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (pre != null && root.val < pre) {
                    return false;
                }
                pre = root.val;
                root = root.right;
            }
        }
        return true;
    }
}
